/**
 * 
 */
package com.gwcloud.leetcode.tags.bfs;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/**
 * @ClassName   : Leetcode0752 
 * @author      : ganwei 
 * @date        : 2020年5月20日
 * @Description : Leetcode0752  打开转盘锁
 */
public class Leetcode0752 {
    /**
     * -解题思路,bfs算法
     */
	public int openLock(String[] deadends, String target) {
    	//记录需要跳过的死亡密码
		Set<String> deads = new HashSet<>();
		for(int i = 0; i < deadends.length; i++){
			deads.add(deadends[i]);
		}
		//记录是否被访问过
		Set<String> visited = new HashSet<>();
		Queue<String> queue = new LinkedList<String>();
    	int step = 0;
    	queue.offer("0000");
    	visited.add("0000");
    	
    	while(!queue.isEmpty()){
    		int length = queue.size();
    		for(int i = 0; i < length; i++){
    			String cur = queue.poll();
    			//判断是否访问过
    			if(deads.contains(cur)){
    				continue;
    			}
    			//判断重点
    			if(cur.equals(target)){
    				return step;
    			}
    			
    			
    			
    			for(int j = 0; j < 4; j++){
                    String up = plusOne(cur, j);
                    if (!visited.contains(up)) {
                        queue.offer(up);
                        visited.add(up);
                    }
                    
                    String down = minusOne(cur, j);
                    if (!visited.contains(down)) {
                        queue.offer(down);
                        visited.add(down);
                    }
    			}
    			
    		}
    		step++;
    	}
		
		
    	return -1;
    }
	
    //将 s[i] 向下拨动一次
	public String plusOne(String s, int j) {
	    char[] ch = s.toCharArray();
	    if (ch[j] == '9')
	        ch[j] = '0';
	    else
	        ch[j] += 1;
	    return new String(ch);
	} 
	
	// 将 s[i] 向下拨动一次
	public String minusOne(String s, int j) {
	    char[] ch = s.toCharArray();
	    if (ch[j] == '0')
	        ch[j] = '9';
	    else
	        ch[j] -= 1;
	    return new String(ch);
	}
	//双向BFS,已知起点和终点，保留曲目
	public int openLock_1(String[] deadends, String target) {
		
		return -1;
	}
    public static void main(String[] args){
    	
    }
}
